package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;

public class SortCharactersByFrequency {
	
	public static void main(String[] args) {
		String s = "abcdderff";
		SortCharactersByFrequency object = new SortCharactersByFrequency();
		System.out.println(object.frequencySort(s));
	}
	
	public String frequencySort(String s) {
		if (s == null) {
			return s;
		}
		char[] chas = s.toCharArray();
		HashMap<Character, Integer> map = new HashMap<>();
		for (int i = 0; i < chas.length; i++) {
			map.put(chas[i], map.getOrDefault(chas[i], 0) + 1);
		}
		// 对map排个序，让出现次数多的排在前面
		List<Entry<Character, Integer>> set =new ArrayList<>(map.entrySet());
		Collections.sort(set, new Comparator<Entry<Character, Integer>>() {
			@Override
			public int compare(Entry<Character, Integer> o1,
					Entry<Character, Integer> o2) {
				//按照从大到小的顺序排
				return o2.getValue() - o1.getValue();
			}
		});
		int index = 0;
		for (Entry<Character, Integer> entry : set) {
			for (int j = 0; j < entry.getValue(); j++) {
				chas[index++] = entry.getKey();
			}
		}
		return String.valueOf(chas);
	}
	
	//上述的还要排序Entry，好麻烦的，后来看discuss，可以是用桶排序的思想
	public String frequencySort2(String s) {
        if(s.length() < 3)
            return s;
        //记录出现的最大次数
        int max = 0;
        int[] map = new int[256];
        for(char ch : s.toCharArray()) {
            map[ch]++;
            max = Math.max(max,map[ch]);
        }
        //buckets里面存储的是所有出现i次的字符
        String[] buckets = new String[max + 1]; // create max buckets
        for(int i = 0 ; i < 256; i++) { // join chars in the same bucket
            String str = buckets[map[i]];
            if(map[i] > 0)
                buckets[map[i]] = (str == null) ? "" + (char)i : (str + (char) i);
        }
        StringBuilder strb = new StringBuilder();
        for(int i = max; i >= 0; i--) { // create string for each bucket.
            if(buckets[i] != null){
            	for(char ch : buckets[i].toCharArray()){
            		//buckets[i]里面所有的字符都出现了i次，所以添加i次即可
            		for(int j = 0; j < i; j++)
            			strb.append(ch);
            	}
            }
        }
        return strb.toString();
    }
}
